import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.List;

/**
 * Clusterer performs mathematical operations on the polled data
 * @author skinner@kth.se
 * @author aidi@kth.se
 */
public class Clusterer extends Thread{
	Hashtable<Integer, List<Long>> xRounds;
	Hashtable<Integer, List<Long>> yRounds;
	int k, repeats, task;

	List<Long> delXt;
	List<Long> delYt;
	int numDeltas;
	boolean useOutputFile;
	
	public Clusterer(Hashtable<Integer, List<Long>> xRounds, Hashtable<Integer, List<Long>> yRounds, 
			int k, int repeats, int task, boolean useOutputFile) {
		this.xRounds = xRounds;
		this.yRounds = yRounds;
		this.k = k;
		this.repeats = repeats;
		this.task = task;
		this.useOutputFile = useOutputFile;
		
		/* Find averages and then compute delta values */
		delXt = createDeltas(createAverages(xRounds, "X"));
		delYt = createDeltas(createAverages(yRounds, "Y"));
		numDeltas = delXt.size();
		/* Output all Deltas - so we can know if we harvested any data or if all routers failed to respond all the time */ 
		for(int i=0; i<numDeltas; i++){			
			System.out.println("Round: " + (i+1) + "\tDelta values (" + delXt.get(i) + "," + delYt.get(i) + ")" );
		}
		
		if (numDeltas > 0) {
			this.start();
		} else {
			System.out.println("No deltas were created, so no clustering was run.");
		}
	}
	
	public void run() {
		// List to hold the DBI value for each round, so we can find the lowest
		List<Double> dbis = new ArrayList<Double>();
		DecimalFormat df = new DecimalFormat("#.##");
		for(int r=0; r<repeats; r++) {
			System.out.println("\nCalculation number: " + (r+1));
			
			/* Randomly select initial centroids */
			List<Integer> initCentroids = new ArrayList<Integer>();
			List<Cluster> initClusters = new ArrayList<Cluster>();
			while(initCentroids.size() < k) {
				int p = (int) (Math.random()*(numDeltas));
				if (!initCentroids.contains(p)) {
					initCentroids.add(p);
					
					Cluster c = new Cluster(delXt.get(p),delYt.get(p));
					initClusters.add(c);
				}
			}
			
			List<Cluster> clusters = cluster(initClusters);
			List<Cluster> newCentroids = getNewCentroids(clusters);
			
			// Keep recalculating until the next round has the same centroids as current centroids (or hit MAX_ITERATIONS)
			int numIterations = 0;
			while (!haveSameCentroids(clusters, newCentroids)) {
				clusters = cluster(newCentroids);
				newCentroids = getNewCentroids(clusters);
				numIterations ++;
				if (numIterations > Start.MAX_CLUSTERING_ITERATIONS)
					break;
			}
			
			// Remove empty clusters & measure largest cluster size
			int maxClusterSize = 0;
			for (Cluster c : clusters) {
				if (c.getNumPoints() == 0) {
					clusters.remove(c);
				}
				if (c.getNumPoints() > maxClusterSize) {
					maxClusterSize = c.getNumPoints();
				}
			}

			/*  Output cluster data */
			for (int i=0; i<k; i++) {			
				System.out.println("Cluster "+ (i+1) +":"
						+ "\tINITIAL CENTROID: (" + initClusters.get(i).getCentroidX() + "," + initClusters.get(i).getCentroidY() + ")"
						+ "\tCENTROID: (" + clusters.get(i).getCentroidX() + "," + clusters.get(i).getCentroidY() + ")"
						+ "\tDistance to origin: " 
						+ (int) Math.sqrt(clusters.get(i).getCentroidX()*clusters.get(i).getCentroidX()
								+ clusters.get(i).getCentroidY()*clusters.get(i).getCentroidY())
						+ "\tsize:" + clusters.get(i).getXs().size());
			}

			/* Calculate DBI's */
			double dbi = calcDbi(clusters);
			System.out.println("DBI: " + df.format(dbi));
			dbis.add(dbi);

			findAttacks(clusters);
			
			if (useOutputFile) {
				/* Write to an output file, so we read those values for building scatter plots */
				SimpleDateFormat format = new SimpleDateFormat("yyyyMMdd_hhmm");
				String fileName = "deltas_" + format.format(new Date()) + "_" + (r + 1) + ".out";
				try {
					FileWriter file = new FileWriter(fileName, false);
					Writer output = new BufferedWriter(file);
					for(int round=0; round<maxClusterSize; round++) {
						String str = "";
						for(Cluster c: clusters) {
							if (c.getNumPoints() > round) {
								str += c.getXs().get(round) +"\t";
								str += c.getYs().get(round) +"\t";
							} else {
								// Tells GnuPlot to skip these vales
								str += "?\t\t?\t\t";
							}
						}
						if(newCentroids.size() > round) {
							str += newCentroids.get(round).getCentroidX() + "\t";
							str += newCentroids.get(round).getCentroidY() + "\t";
						}
						output.write(str + "\r\n");
					}			
					output.close();
				} catch (IOException e) {
					System.err.println("Error writing to output file: " + fileName );
				}
			}
		}
		
		double minDbi = dbis.get(0);
		int minDbiCalcRound = 0;
		for(int i=0; i<dbis.size(); i++){
			if (dbis.get(i) < minDbi) {
				minDbi = dbis.get(i);
				minDbiCalcRound = i;
			}
		}

		System.out.println("\nThe calculation with the mininum Davies-Bouldin Index occurred in clustering round: " 
				+ (minDbiCalcRound + 1) + " with DBI: " + df.format(minDbi));

	}
	
	public boolean haveSameCentroids(List<Cluster> c1, List<Cluster> c2) {
		int numConverged = 0;
		if( c1.size() == c2.size()) {
			for (int i=0; i< c1.size(); i++) {
				if (c1.get(i).getCentroidX() == c2.get(i).getCentroidX()
						&& c1.get(i).getCentroidY() == c2.get(i).getCentroidY()) {
					numConverged++;
				}
			}
			if (numConverged == c1.size()) {
				return true;
			}
		}
		return false;
	}
	
	public List<Cluster> cluster(List<Cluster> clusters) {		
		/* Go through all points, and choose which cluster to add to based on Euclidean distance to its centroid */
		for(int t=0; t<numDeltas; t++) {
			/* First find distance to each centroid from selected point */
			List<Long> distances = new ArrayList<Long>();
			for(Cluster c: clusters) {
				distances.add( (long) Math.sqrt(
						(delXt.get(t) - c.getCentroidX())*(delXt.get(t) -  c.getCentroidX())
						+(delYt.get(t) - c.getCentroidY()) *(delYt.get(t) -  c.getCentroidY()) ) );
				//System.out.println("Round (" + t + "):\tDistance to centroid " + (distances.size() - 1) + ":\t" + distances.get(distances.size() - 1));
			}

			/* Then compare the distances to discover which centroid is nearest */
			int nearestCluster = -1;
			long distToCentroid = -1;
			for(int i=0; i<distances.size(); i++) {
				if (distToCentroid == -1 || (distances.get(i) < distToCentroid)) {
					nearestCluster = i;
					distToCentroid = distances.get(i);
				}
			}
			
			clusters.get(nearestCluster).getXs().add(delXt.get(t));
			clusters.get(nearestCluster).getYs().add(delYt.get(t));	
			clusters.get(nearestCluster).getRounds().add(t);
		}		
		
		return clusters;
	}
	
	public double calcDbi(List<Cluster> clusters) {		
		List<Double> sigmas = new ArrayList<Double>();
		for(Cluster c1 : clusters) {
			double sigma = 0;
			// Go through every point (X,Y) and sum the distance to the centroid
			for(int i=0; i<c1.getNumPoints(); i++) {
				sigma += Math.sqrt( (c1.getXs().get(i) - c1.getCentroidX())*(c1.getXs().get(i) - c1.getCentroidX())
						+ (c1.getYs().get(i) - c1.getCentroidY())*(c1.getYs().get(i) - c1.getCentroidY()));
			}
			// Average over number of points
			sigma /= c1.getNumPoints();
			
			// Add to list
			sigmas.add(sigma);
		}
	
		/*  Determine the Davies-Bouldin Index and output to user */
		double dbi = 0;
		for (int i=0; i<k; i++) {			
			double valijMax = 0;
			for(int j=0; j<k; j++) {					
				if (j != i) {
					// Calculate the distance from cluster i's centroid ci to cluster j's centroid cj
					double dcicj = Math.sqrt( ((clusters.get(i).getCentroidX() - clusters.get(j).getCentroidX())
													* (clusters.get(i).getCentroidX() - clusters.get(j).getCentroidX()))
												+ ((clusters.get(i).getCentroidY() - clusters.get(j).getCentroidY())
													*(clusters.get(i).getCentroidY() - clusters.get(j).getCentroidY())));
					// The value we are trying to get the maximum of is the sum of the sigmas over the distance
					double valij = (sigmas.get(i) + sigmas.get(j))/dcicj;
					if (valij > valijMax) {
						valijMax = valij;
					}						
				}					
			}
			
			// Once we find the max of these values add it to the sum
			dbi += valijMax;
		}
		
		// Normalize sum by number of clusters
		dbi /= k;
		
		return dbi;
	}
	
	public void findAttacks(List<Cluster> clusters) {
		/* Determine which are the top two clusters based on centroid value */
		long largestCentroid = 0;
		int largestCentroidCluster = 0;
		long secondLargestCentroid = 0;
		int secondLargestCentroidCluster = 0;			
		for (int i=0; i<k; i++) {
			 if (clusters.get(i).getDistance() > largestCentroid) {
				 largestCentroid = clusters.get(i).getDistance();
				 largestCentroidCluster = i;
			 }
		}
		for(int i=0; i<k; i++) {
			 if (clusters.get(i).getDistance() > secondLargestCentroid && i!=largestCentroidCluster) {
				 secondLargestCentroid = clusters.get(i).getDistance();
				 secondLargestCentroidCluster = i;
			 }
		}
		
		/* Determine if there was an attack by the requisites given in the project description */
		if(clusters.get(largestCentroidCluster).getNumPoints() < clusters.get(secondLargestCentroidCluster).getNumPoints()) {
			System.out.println("There was a DoS attack in cluster: \t" + (largestCentroidCluster + 1));
			System.out.print("-Rounds: ");
			for(int i: clusters.get(largestCentroidCluster).getRounds()) {
				System.out.print(i + " ");
			}
			
			System.out.println("\nThere was a port scan attack in cluster: " + (secondLargestCentroidCluster + 1));
			System.out.print("-Rounds: ");
			for(int i: clusters.get(secondLargestCentroidCluster).getRounds()) {
				System.out.print(i + " ");
			}
			
			System.out.println("");	
		} else {
			System.out.println("Unable to positively identify attacks due to cluster sizes and centroid values.");
		}
	}
	
	
	/**
	 * Simple function to find an average value from a list of values
	 * @param values
	 * @return the average or -1 if the list was empty
	 */
	public long getAverage(List<Long> values) {
		if (!values.isEmpty()) {
			long sum = 0;
			for(long v: values){
				sum += v;
			}
			return sum/values.size();
		} else {
			return -1;
		}
	}
	
	/**
	 * Simple function to find an average value from a list of values
	 * @param values
	 * @return the average or -1 if the list was empty
	 */
	public List<Cluster> getNewCentroids(List<Cluster> oldClusters) {
		List<Cluster> newCentroids = new ArrayList<Cluster>();
		
		for (Cluster c: oldClusters) {
			long newX = 0;
			long newY = 0;
			if ( c.getNumPoints() > 0) {
				for (Long x: c.getXs()) {
					newX +=x;
				}
				for (Long y: c.getYs()) {
					newY +=y;
				}
				newX /= c.getXs().size();
				newY /= c.getYs().size();
			}
			Cluster newCentroid = new Cluster(newX, newY);
			newCentroids.add(newCentroid);
		}
		
		return newCentroids;
	}
	
	/**
	 * Find the changes between values in a list
	 * @param avgs
	 * @return a list of the delta values, will be one less than the original list
	 */
	public List<Long> createDeltas(List<Long> avgs) {
		List<Long> dels = new ArrayList<Long>();
		for (int i=1; i<avgs.size(); i++) {
			dels.add(Math.abs(avgs.get(i) - avgs.get(i-1)));
		}
		return dels;
	}

	/**
	 * Finds the averages for each round by going through each round's list
	 * @param rounds
	 * @param var
	 * @return
	 */
	public List<Long> createAverages( Hashtable<Integer,List<Long>> rounds, String var) {
		List<Long> avgs = new ArrayList<Long>();
		Enumeration<Integer> e = rounds.keys();
		while (e.hasMoreElements() ) {
			int round = e.nextElement();
			List<Long> roundList =  rounds.get(round);
			
			if (roundList.size() > 0) {			
				avgs.add(getAverage(roundList));
			} else {
				/* On the off chance that no routers respond to our query in this round, we set a flag */
				System.err.println("No values were collected for " + var + " MIB for round " + round);
				avgs.add(-1l);
			}
			//System.out.println("Average X(" + round + "): " + avgX + "\tNumRouters: " + roundList.size());
		}
		
		return avgs;
	}
}

/**
 * Cluster class models all the data associated with a cluster
 * @author skinner@kth.se
 * @author aidi@kth.se
 */
class Cluster {
	private List<Long> xs = new ArrayList<Long>();
	private List<Long> ys = new ArrayList<Long>();
	private List<Integer> rounds = new ArrayList<Integer>();
	private long centroidX;
	private long centroidY;
	private long distance = 0;
	
	public Cluster(long centroidX, long centroidY) {
		this.centroidX = centroidX;
		this.centroidY = centroidY;
		
		distance = (int) Math.sqrt((centroidX * centroidX) + (centroidY * centroidY));
	}
	
	public int getNumPoints() {
		return rounds.size();
	}

	public List<Integer> getRounds() {
		return rounds;
	}
	public void setRounds(List<Integer> rounds) {
		this.rounds = rounds;
	}

	public List<Long> getXs() {
		return xs;
	}
	public void setXs(List<Long> xs) {
		this.xs = xs;
	}
	
	public List<Long> getYs() {
		return ys;
	}
	public void setYs(List<Long> ys) {
		this.ys = ys;
	}
	
	public long getCentroidX() {
		return centroidX;
	}
	public void setCentroidX(long centroidX) {
		this.centroidX = centroidX;
	}
	
	public long getCentroidY() {
		return centroidY;
	}
	public void setCentroidY(long centroidY) {
		this.centroidY = centroidY;
	}

	public long getDistance() {
		return distance;
	}

	public void setDistance(long distance) {
		this.distance = distance;
	}
}
